package com.lihepeng.leecode.tree.langbuladong;

import com.lihepeng.leecode.tree.TreeNode;
import org.junit.Test;

import java.util.LinkedList;

/**
 * HEAD
 * 序列化和反序列化二叉树
 * 序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。
 *
 * 请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
 *
 * 提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * 使用前序遍历的方式完成
 */
public class Solution297 {
    // Encodes a tree to a single string.
    private static final String SEP = ",";
    private static final String EMPTY = "#";
    StringBuffer sb = new StringBuffer();
    public String serialize(TreeNode root) {

        if (root==null){
            sb.append(EMPTY).append(SEP);
        }else {
            sb.append(root.val).append(SEP);
            serialize(root.left);
            serialize(root.right);
        }

        return sb.toString();
    }


    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        // 将字符串转换成列表
        LinkedList<String>nodes = new LinkedList<>();
        for (String item:data.split(",")) {
            nodes.add(item);
        }
        return deserialize(nodes);
    }

    public TreeNode deserialize(LinkedList<String> nodes ) {
        // 需要找到根节点
        if (nodes.isEmpty()){
            return null;
        }
        // 列表最左边的元素为根节点
        String s = nodes.removeFirst();
        if (EMPTY.equals(s)){
            return null;
        }
        TreeNode rootNode = new TreeNode(Integer.parseInt(s));
        rootNode.left = deserialize(nodes);
        rootNode.right = deserialize(nodes);
        return rootNode;
    }

    @Test
    public void test(){
        TreeNode treeNode = new TreeNode(0);
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        treeNode.left=treeNode1;
        treeNode1.left = treeNode2;
        treeNode1.right = treeNode3;
        treeNode3.right=treeNode4;
        treeNode.right = treeNode5;
        String serialize = this.serialize(treeNode);
        System.out.println(serialize);

        TreeNode deserialize = this.deserialize(serialize);
        System.out.println(deserialize);
    }
}
